package cn.bellychang.leetcode.question020;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
 * <p>
 * An input string is valid if:
 * <p>
 * Open brackets must be closed by the same type of brackets.
 * Open brackets must be closed in the correct order.
 * Note that an empty string is also considered valid.
 *
 * @author: bellychang
 * @date: 2020/2/16
 */
class Solution {

    public boolean isValid(String s) {
        if ("".equals(s)) {
            return true;
        }

        ArrayList<Character> openBrackets = new ArrayList<>();
        openBrackets.add('(');
        openBrackets.add('{');
        openBrackets.add('[');

        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (openBrackets.contains(aChar)) {
                stack.push(aChar);
            } else {
                if (!stack.isEmpty()) {
                    Character topChar = stack.pop();
                    if (aChar == ')' && topChar == '(') {
                        continue;
                    } else if (aChar == '}' && topChar == '{') {
                        continue;
                    } else if (aChar == ']' && topChar == '[') {
                        continue;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}
